package com.yangzhe.algorithm.c028;

// 基数排序，acm练习风格
// 测试链接 : https://www.luogu.com.cn/problem/P1177
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

import java.io.*;

public class RadixSort_Acm {

    private static int MAX_LENGTH = 100001;

    private static int n = 0;

    private static int[] nums = new int[MAX_LENGTH];

    public static void main(String[] args) throws IOException {
        try (
                InputStreamReader inputReader = new InputStreamReader(System.in);
                BufferedReader reader = new BufferedReader(inputReader);
        ) {
            StreamTokenizer token = new StreamTokenizer(reader);
            token.nextToken();
            n = (int)token.nval;

            for (int i = 0; i < n; i++) {
                token.nextToken();
                nums[i] = (int)token.nval;
            }
        }

        radisSort();

        try(
                OutputStreamWriter outputStream = new OutputStreamWriter(System.out);
                PrintWriter print = new PrintWriter(outputStream);
        ) {
            for (int i = 0; i < n - 1; i++) {
                print.print(nums[i] + " ");
            }
            print.print(nums[n - 1]);
            print.flush();
        }
    }

    /**
     * 第一种排序：
     * 1. 从顶到底建立大根堆 复杂度 O(n * logn)
     * 2. 建堆后调整 复杂度 O(n * logn)
     * 整体复杂度 O(n * logn)
     */
    public static void heapSort1() {
        // 1. 从顶到底建立大根堆
        for (int i = 0; i < n; i++) {
            heapInsert(i);
        }

        int size = n;
        // 2. 依次弹出最大值，再次建立大根堆
        while(size > 0) {
            swap(0, --size);
            heapify(0, size);
        }
    }

    /**
     * 第二种排序：
     * 1. 从底到顶建立大根堆 复杂度 O(n)
     * 2. 建堆后调整 复杂度 O(n * logn)
     * 整体复杂度 O(n * logn)
     */
    public static void heapSort2() {
        // 1. 从底到顶建立大根堆
        for (int i = n - 1; i >= 0; i--) {
            heapify(i, n);
        }

        int size = n;
        // 2. 依次弹出最大值，再次建立大根堆
        while(size > 0) {
            swap(0, --size);
            heapify(0, size);
        }
    }

    public static void heapInsert(int index) {
        // 父节点index = (index - 1) / 2;
        // 如果当前节点比父节点大，则和父节点交换，即向上调整
        while(nums[(index -1) / 2] < nums[index]) {
            swap((index -1) / 2, index);
            index = (index -1) / 2;
        }

    }

    public static void heapify(int index, int size) {
        // 左孩子index = 2index + 1;
        // 右孩子index = 2index + 2;
        // 当前节点比孩子节点小，则和孩子节点中大的那个交换，即向下调整
        while(2 * index + 1 < size) {
            int maxChildIndex = (2 * index + 2 < size) && nums[2 * index + 2] > nums[2 * index + 1] ? (2 * index + 2) : (2 * index + 1);
            if (nums[maxChildIndex] > nums[index]) {
                swap(maxChildIndex, index);
                index = maxChildIndex;
            } else {
                break;
            }
        }
    }

    /**
     * 基数排序基于多少进制做
     * 进制越高，所需的轮数就越少
     */
    private static int BASE = 10;

    private static int[] help = new int[MAX_LENGTH];

    /**
     * 进制下，<= 每个数字的个数
     */
    private static int[] numFrequency = new int[BASE];

    /**
     * 基数排序
     * 只支持基于数字的排序，且流程本身不支持负数，需要特殊处理
     */
    public static void radisSort() {
        // 1. 获取数组中最小值
        int minValue = nums[0];
        for(int i = 1; i < n; i++) {
            minValue = Math.min(minValue, nums[i]);
        }
        // 2. 如果存在负数，则需要把数组全部转成正整数，同时获取数组最大值，判断需要做多少轮
        boolean existNegativeValue = minValue < 0;
        // 所有的数减去最小的负值都会 >= 0
        int maxValue;
        if (existNegativeValue) {
            maxValue = nums[0] - minValue;
            for (int i = 0; i < n; i++) {
                nums[i] = nums[i] - minValue;
                maxValue = Math.max(maxValue, nums[i]);
            }
        } else {
            maxValue = nums[0];
            for (int i = 0; i < n; i++) {
                maxValue = Math.max(maxValue, nums[i]);
            }
        }

        // 3. 判断需要做多少轮
        int bits = countBits(maxValue);

        // 4. 进行基数排序
        realRadisSort(bits, BASE);
        // 5. 如果存在负数，则需要还原数组
        if (existNegativeValue) {
            for (int i = 0; i < n; i++) {
                nums[i] = nums[i] + minValue;
            }
        }
    }

    public static void realRadisSort(int bits, int base) {
        // 先按最低为排序，逐渐排到最高位，如果是十进制，则 个 十 百 千 .....
        int offset = 1;
        for (int bit = 1; bit <= bits; bit++) {
            // 统计每个位数数字的词频
            for (int i = 0; i < n; i++) {
                int value = (nums[i] / offset) % base;
                numFrequency[value]++;
            }

            // 让每个位数的词频转换为 <= 这个数字的个数
            for (int i = 1; i < base; i++ ) {
                numFrequency[i] = numFrequency[i - 1] + numFrequency[i];
            }

            // 根据 <= 这个数字的个数的表，将原数组按位排序的结果放入到help中，需要倒着遍历原数组
            for (int i = n - 1; i >= 0; i--) {
                // 取这个数字的当前的位数
                int value = (nums[i] / offset) % base;
                // 如果是10进制，例如<=9的有8个，则这个数字应该放在数组的 7 位置，下一次遇到9则放在6位置
                numFrequency[value] = numFrequency[value] - 1;
                help[numFrequency[value]] = nums[i];
            }

            // 将这一轮按位排好序的数组刷回原数组
            for (int i = 0; i < n; i++) {
                nums[i] = help[i];
            }

            // 清空词频表
            numFrequency = new int[base];
            // 进一位
            offset = offset * base;
        }
    }

    /**
     * 计算数字位数
     */
    public static int countBits(int num) {
        int bits = 0;
        int offset = 1;
        int value = num / offset;
        while(value != 0) {
            bits++;
            offset = offset * BASE;
            value = num / offset;;
        }

        return bits;
    }

    public static void swap(int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}